import java.util.Stack;

// 这个类主要是为了解决最小栈相关的问题
// 测试链接 : https://leetcode.cn/problems/min-stack/
public class GetMinStack {

    // 这里定义了一个内部类MinStack1，它实现了一种最小栈的结构
    // 在提交时需要把类名、构造方法改成MinStack
    class MinStack1 {
        // data栈用于存储所有压入栈的数据
        public Stack<Integer> data;
        // min栈用于存储当前的最小值
        public Stack<Integer> min;

        // 构造方法，用于初始化data栈和min栈
        public MinStack1() {
            data = new Stack<Integer>();
            min = new Stack<Integer>();
        }

        // 压入元素的方法
        public void push(int val) {
            // 先将元素压入data栈
            data.push(val);
            // 如果min栈为空或者要压入的值小于等于min栈的栈顶元素
            if (min.isEmpty() || val <= min.peek()) {
                // 则将该值也压入min栈，因为它可能是新的最小值
                min.push(val);
            } else {
                // 如果不是新的最小值，就将min栈的栈顶元素再次压入min栈
                // 这样可以保证min栈的元素个数和data栈相同，并且min栈的栈顶元素始终是当前的最小值
                min.push(min.peek());
            }
        }

        // 弹出元素的方法
        public void pop() {
            // 同时弹出data栈和min栈的栈顶元素
            data.pop();
            min.pop();
        }

        // 获取data栈栈顶元素的方法
        public int top() {
            return data.peek();
        }

        // 获取当前最小值的方法，也就是min栈的栈顶元素
        public int getMin() {
            return min.peek();
        }
    }

    // 这里定义了另一个内部类MinStack2，它是另一种实现最小栈的方式
    // 在提交时需要把类名、构造方法改成MinStack
    class MinStack2 {
        // 这里定义了一个常量MAXN，用于限制栈的大小
        // 根据几次提交实验得出，这个值在leetcode测试时，同时在栈里的数据不会超过这个值
        // 如果leetcode补测试数据导致超过这个量出错，就需要调大这个值
        public final int MAXN = 8001;

        // data数组用于存储压入栈的数据
        public int[] data;
        // min数组用于存储当前的最小值
        public int[] min;
        // size变量用于记录当前栈中元素的个数
        int size;

        // 构造方法，用于初始化data数组、min数组和size变量
        public MinStack2() {
            data = new int[MAXN];
            min = new int[MAXN];
            size = 0;
        }

        // 压入元素的方法
        public void push(int val) {
            // 将元素存入data数组中
            data[size] = val;
            // 如果栈为空或者要压入的值小于等于min数组中当前记录的最小值
            if (size == 0 || val <= min[size - 1]) {
                // 则将该值存入min数组中，作为新的最小值
                min[size] = val;
            } else {
                // 如果不是新的最小值，就将min数组中当前记录的最小值再次存入min数组
                min[size] = min[size - 1];
            }
            // 栈中元素个数加1
            size++;
        }

        // 弹出元素的方法，只需要将size减1即可
        public void pop() {
            size--;
        }

        // 获取栈顶元素的方法，返回data数组中索引为size - 1的元素
        public int top() {
            return data[size - 1];
        }

        // 获取当前最小值的方法，返回min数组中索引为size - 1的元素
        public int getMin() {
            return min[size - 1];
        }
    }
}